public class Leetcode {
}

class Solution1 {
    public int combinationSum4(int[] nums, int target) {
        int n = nums.length;
        //创建一个dp表，表示凑成总和为i的排列数一个有多少
        int[] dp = new int[target+1];
        dp[0] = 1;
        for(int i = 1; i <= target; i++){
            for(int j = 0; j < n; j++){
                //选择j位置的元素，我们必须要确保i的值要大于等于nums[j]的值，保证是可以凑成i的
                if(i >= nums[j]){
                    dp[i] += dp[i-nums[j]];
                }
            }
        }
        return dp[target];
    }
}

class Solution2 {
    public int numTrees(int n) {
        //创建一个dp表，表示i个节点的二叉搜索树个数
        int[] dp = new int[n+1];
        dp[0] = 1;
        for(int i = 1; i <= n; i++){
            //利用循环，表示以j位置为根节点此时i个结点二叉树搜素树的个数
            for(int j = 1; j <= i; j++){
                //如果以j为根节点，那么它左子树的结点个数就为j-1,右子树的个数就为i-j,那么此时以j为根节点的且一共有i个结点的二叉搜素树的个数就为，左子树的以j-1个节点的二叉搜素树个数乘于右子树的以i-j个节点的二叉搜素树个数。
                dp[i] += dp[j-1]*dp[i-j];//最后将以所有节点为根节点的二叉树搜素树的个数相加就是总共有i个节点所形成的所有二叉搜索树的个数
            }

        }
        return dp[n];
    }
}